Back to course home
0% completed
Vote For New Content
Analyzing Recursive Algorithms
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Data Structures and Complexity Analysis
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Practical Applications and Case Studies
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Quadratic Space: O(n²)
Quadratic Space Complexity
Key Characteristics
In an algorithm with
- Memory usage grows with the square of the input size.
- This is typical in algorithms that use a 2D array or matrix to store information for each pair of elements or each cell in a grid.
Code Example: Longest Common Subsequence (LCS)
The Longest Common Subsequence (LCS) problem is a classic DP problem where we use a 2D table to store the length of the longest common subsequence between prefixes of two strings.
Java
Saved to Cloud
. . . .
- Explanation:
- The
dptable has dimensions(m+1) x (n+1), wheremandnare the lengths of the two stringsXandY. - Each cell
dp[i][j]stores the length of the LCS of the prefixesX[0...i-1]andY[0...j-1]. - This results in a quadratic space complexity of
.
- The
Examples of Space Operations
- Dynamic Programming on Grids: Problems that involve 2D grids, like pathfinding in a matrix.
- Pair-Based DP Problems: Problems like LCS or edit distance, where we track values for each combination of positions in two strings.
- Graph Algorithms with Adjacency Matrices: Representing a graph with an adjacency matrix uses
space for a graph with nodes.
Linear Space: O(n)
Quiz
Mark as Completed
On this page
Key Characteristics
Code Example: Longest Common Subsequence (LCS)
Examples of